package leetcode.dynamic_programming;

/**
 * @author mgl
 * @version 1.0
 * @description TODO leetCode 746题
 * @date 2023/9/23 10:49
 */
public class MinCostClimbingStairs {

    /**
     * @description 错误解法
     * @param cost  当前层到上一层或两层的花费
     * @return int 最终需要花费的金额
     * @author mgl
     * @date 2023/9/23 11:09
     */
    public int minCostClimbingStairs_err(int[] cost){
        int money = 0;
        int n = cost.length -1;
        while (n > 0) {
            int cost1 = cost[n];
            int cost2 = cost[n-1];

            if (cost1 < cost2) {
                n--;
                money+= cost1;
            }
            else{
                n-=2;
                money += cost2;
            }
        }

        return money;
    }

    public int minCostClimbingStairs(int[] cost){
        int length = cost.length;
        if (length ==2) return Math.min(cost[0],cost[1]);
        int[] dp = new int[length+1];
        dp[0] = 0;
        dp[1] = 0;
        int money = 0;

        for (int i = 2; i < dp.length; i++) {
            money = Math.min(dp[i-1] + cost[i-1],
                    dp[i-2] + cost[i-2]);
            dp[i] = money;
        }

        return money;
    }

    public static void main(String[] args) {
        System.out.println(new MinCostClimbingStairs()
                .minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
    }
}
